<!doctype html>



  


<html class="theme-next pisces use-motion">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>



<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />












  
  
  <link href="/vendors/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />




  
  
  
  

  
    
    
  

  

  

  

  

  
    
    
    <link href="//fonts.googleapis.com/css?family=Lato:300,300italic,400,400italic,700,700italic&subset=latin,latin-ext" rel="stylesheet" type="text/css">
  






<link href="/vendors/font-awesome/css/font-awesome.min.css?v=4.4.0" rel="stylesheet" type="text/css" />

<link href="/css/main.css?v=5.0.1" rel="stylesheet" type="text/css" />


  <meta name="keywords" content="crossoverJie, Java" />





  <link rel="alternate" href="/atom.xml" title="crossoverJie's Blog" type="application/atom+xml" />




  <link rel="shortcut icon" type="image/x-icon" href="/favicon.ico?v=5.0.1" />






<meta name="description" content="前言LRU 是 Least Recently Used 的简写，字面意思则是最近最少使用。
通常用于缓存的淘汰策略实现，由于缓存的内存非常宝贵，所以需要根据某种规则来剔除数据保证内存不被撑满。
如常用的 Redis 就有以下几种策略：



策略
描述




volatile-lru
从已设置过期时间的数据集中挑选最近最少使用的数据淘汰


volatile-ttl
从已设置过期时间的数据集中">
<meta property="og:type" content="article">
<meta property="og:title" content="动手实现一个 LRU cache">
<meta property="og:url" content="http://crossoverjie.top/2018/04/07/algorithm/LRU-cache/index.html">
<meta property="og:site_name" content="crossoverJie's Blog">
<meta property="og:description" content="前言LRU 是 Least Recently Used 的简写，字面意思则是最近最少使用。
通常用于缓存的淘汰策略实现，由于缓存的内存非常宝贵，所以需要根据某种规则来剔除数据保证内存不被撑满。
如常用的 Redis 就有以下几种策略：



策略
描述




volatile-lru
从已设置过期时间的数据集中挑选最近最少使用的数据淘汰


volatile-ttl
从已设置过期时间的数据集中">
<meta property="og:image" content="https://i.loli.net/2019/05/08/5cd1d7b5984ac.jpg">
<meta property="og:image" content="https://i.loli.net/2019/05/08/5cd1d7b842ebd.jpg">
<meta property="og:image" content="https://i.loli.net/2019/05/08/5cd1d7bace008.jpg">
<meta property="og:image" content="https://i.loli.net/2019/05/08/5cd1d7bdae29e.jpg">
<meta property="og:image" content="https://i.loli.net/2019/05/08/5cd1d7bf974c6.jpg">
<meta property="og:image" content="https://i.loli.net/2019/05/08/5cd1d7c26fee5.jpg">
<meta property="og:image" content="https://i.loli.net/2019/05/08/5cd1d7c54a763.jpg">
<meta property="og:updated_time" content="2019-05-07T19:09:41.556Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="动手实现一个 LRU cache">
<meta name="twitter:description" content="前言LRU 是 Least Recently Used 的简写，字面意思则是最近最少使用。
通常用于缓存的淘汰策略实现，由于缓存的内存非常宝贵，所以需要根据某种规则来剔除数据保证内存不被撑满。
如常用的 Redis 就有以下几种策略：



策略
描述




volatile-lru
从已设置过期时间的数据集中挑选最近最少使用的数据淘汰


volatile-ttl
从已设置过期时间的数据集中">
<meta name="twitter:image" content="https://i.loli.net/2019/05/08/5cd1d7b5984ac.jpg">



<script type="text/javascript" id="hexo.configuration">
  var NexT = window.NexT || {};
  var CONFIG = {
    scheme: 'Pisces',
    sidebar: {"position":"left","display":"post"},
    fancybox: true,
    motion: true,
    duoshuo: {
      userId: 555390,
      author: 'crossoverJie'
    }
  };
</script>




  <link rel="canonical" href="http://crossoverjie.top/2018/04/07/algorithm/LRU-cache/"/>

  <title> 动手实现一个 LRU cache | crossoverJie's Blog </title>
</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="en">

  








  <div style="display: none;">
    <script src="https://s6.cnzz.com/stat.php?id=1259025147&web_id=1259025147" type="text/javascript"></script>
  </div>





  
  
    
  

  <div class="container one-collumn sidebar-position-left page-post-detail ">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-meta ">
  

  <div class="custom-logo-site-title">
    <a href="/"  class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <span class="site-title">crossoverJie's Blog</span>
      <span class="logo-line-after"><i></i></span>
    </a>
  </div>
  <p class="site-subtitle">baller</p>
</div>

<div class="site-nav-toggle">
  <button>
    <span class="btn-bar"></span>
    <span class="btn-bar"></span>
    <span class="btn-bar"></span>
  </button>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br />
            
            Home
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br />
            
            Categories
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br />
            
            About
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br />
            
            Archives
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br />
            
            Tags
          </a>
        </li>
      
        
        <li class="menu-item menu-item-photo">
          <a href="/favourite" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-photo"></i> <br />
            
            photo
          </a>
        </li>
      
        
        <li class="menu-item menu-item-jcsprout">
          <a href="https://crossoverjie.top/JCSprout/#/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-leaf"></i> <br />
            
            JCSprout
          </a>
        </li>
      
        
        <li class="menu-item menu-item-cicada">
          <a href="https://github.com/TogetherOS/cicada" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-github"></i> <br />
            
            cicada
          </a>
        </li>
      
        
        <li class="menu-item menu-item-cim">
          <a href="https://github.com/crossoverjie/cim" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-far fa-comment"></i> <br />
            
            CIM
          </a>
        </li>
      
        
        <li class="menu-item menu-item-vlog">
          <a href="https://space.bilibili.com/42339430" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-youtube"></i> <br />
            
            Vlog
          </a>
        </li>
      

      
        <li class="menu-item menu-item-search">
          
            <a href="#" class="popup-trigger">
          
            
              <i class="menu-item-icon fa fa-search fa-fw"></i> <br />
            
            Search
          </a>
        </li>
      
    </ul>
  

  
    <div class="site-search">
      
  <div class="popup">
 <span class="search-icon fa fa-search"></span>
 <input type="text" id="local-search-input">
 <div id="local-search-result"></div>
 <span class="popup-btn-close">close</span>
</div>


    </div>
  
</nav>

 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  
  

  
  
  

  <article class="post post-type-normal " itemscope itemtype="http://schema.org/Article">

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
            
            
              
                动手实现一个 LRU cache
              
            
          </h1>
        

        <div class="post-meta">
          <span class="post-time">
            <span class="post-meta-item-icon">
              <i class="fa fa-calendar-o"></i>
            </span>
            <span class="post-meta-item-text">Posted on</span>
            <time itemprop="dateCreated" datetime="2018-04-07T01:01:36+08:00" content="2018-04-07">
              2018-04-07
            </time>
          </span>

          
            <span class="post-category" >
              &nbsp; | &nbsp;
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              <span class="post-meta-item-text">In</span>
              
                <span itemprop="about" itemscope itemtype="https://schema.org/Thing">
                  <a href="/categories/算法/" itemprop="url" rel="index">
                    <span itemprop="name">算法</span>
                  </a>
                </span>

                
                
                  , 
                

              
                <span itemprop="about" itemscope itemtype="https://schema.org/Thing">
                  <a href="/categories/算法/LRU-cache/" itemprop="url" rel="index">
                    <span itemprop="name">LRU cache</span>
                  </a>
                </span>

                
                

              
            </span>
          

          
            
              <span class="post-comments-count">
                &nbsp; | &nbsp;
                <a href="/2018/04/07/algorithm/LRU-cache/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count disqus-comment-count" data-disqus-identifier="2018/04/07/algorithm/LRU-cache/" itemprop="commentsCount"></span>
                </a>
              </span>
            
          

          

          
          
             <span id="/2018/04/07/algorithm/LRU-cache/" class="leancloud_visitors" data-flag-title="动手实现一个 LRU cache">
               &nbsp; | &nbsp;
               <span class="post-meta-item-icon">
                 <i class="fa fa-eye"></i>
               </span>
               <span class="post-meta-item-text">visitors </span>
               <span class="leancloud-visitors-count"></span>
              </span>
          

          
              &nbsp; | &nbsp;
              <span class="page-pv">本文总阅读量
              <span class="busuanzi-value" id="busuanzi_value_page_pv" ></span>次
              </span>
          
        </div>
      </header>
    


    <div class="post-body" itemprop="articleBody">

      
      

      
        <p><img src="https://i.loli.net/2019/05/08/5cd1d7b5984ac.jpg" alt=""></p>
<h2 id="前言"><a href="#前言" class="headerlink" title="前言"></a>前言</h2><p>LRU 是 <code>Least Recently Used</code> 的简写，字面意思则是<code>最近最少使用</code>。</p>
<p>通常用于缓存的淘汰策略实现，由于缓存的内存非常宝贵，所以需要根据某种规则来剔除数据保证内存不被撑满。</p>
<p>如常用的 Redis 就有以下几种策略：</p>
<table>
<thead>
<tr>
<th style="text-align:center">策略</th>
<th style="text-align:center">描述</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center">volatile-lru</td>
<td style="text-align:center">从已设置过期时间的数据集中挑选最近最少使用的数据淘汰</td>
</tr>
<tr>
<td style="text-align:center">volatile-ttl</td>
<td style="text-align:center">从已设置过期时间的数据集中挑选将要过期的数据淘汰</td>
</tr>
<tr>
<td style="text-align:center">volatile-random</td>
<td style="text-align:center">从已设置过期时间的数据集中任意选择数据淘汰</td>
</tr>
<tr>
<td style="text-align:center">allkeys-lru</td>
<td style="text-align:center">从所有数据集中挑选最近最少使用的数据淘汰</td>
</tr>
<tr>
<td style="text-align:center">allkeys-random</td>
<td style="text-align:center">从所有数据集中任意选择数据进行淘汰</td>
</tr>
<tr>
<td style="text-align:center">no-envicition</td>
<td style="text-align:center">禁止驱逐数据</td>
</tr>
</tbody>
</table>
<blockquote>
<p>摘抄自:<a href="https://github.com/CyC2018/Interview-Notebook/blob/master/notes/Redis.md#%E5%8D%81%E4%B8%89%E6%95%B0%E6%8D%AE%E6%B7%98%E6%B1%B0%E7%AD%96%E7%95%A5" target="_blank" rel="external">https://github.com/CyC2018/Interview-Notebook/blob/master/notes/Redis.md#%E5%8D%81%E4%B8%89%E6%95%B0%E6%8D%AE%E6%B7%98%E6%B1%B0%E7%AD%96%E7%95%A5</a></p>
</blockquote>
<a id="more"></a>
<h2 id="实现一"><a href="#实现一" class="headerlink" title="实现一"></a>实现一</h2><p>之前也有接触过一道面试题，大概需求是：</p>
<ul>
<li>实现一个 LRU 缓存，当缓存数据达到 N 之后需要淘汰掉最近最少使用的数据。</li>
<li>N 小时之内没有被访问的数据也需要淘汰掉。</li>
</ul>
<p>以下是我的实现：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div><div class="line">55</div><div class="line">56</div><div class="line">57</div><div class="line">58</div><div class="line">59</div><div class="line">60</div><div class="line">61</div><div class="line">62</div><div class="line">63</div><div class="line">64</div><div class="line">65</div><div class="line">66</div><div class="line">67</div><div class="line">68</div><div class="line">69</div><div class="line">70</div><div class="line">71</div><div class="line">72</div><div class="line">73</div><div class="line">74</div><div class="line">75</div><div class="line">76</div><div class="line">77</div><div class="line">78</div><div class="line">79</div><div class="line">80</div><div class="line">81</div><div class="line">82</div><div class="line">83</div><div class="line">84</div><div class="line">85</div><div class="line">86</div><div class="line">87</div><div class="line">88</div><div class="line">89</div><div class="line">90</div><div class="line">91</div><div class="line">92</div><div class="line">93</div><div class="line">94</div><div class="line">95</div><div class="line">96</div><div class="line">97</div><div class="line">98</div><div class="line">99</div><div class="line">100</div><div class="line">101</div><div class="line">102</div><div class="line">103</div><div class="line">104</div><div class="line">105</div><div class="line">106</div><div class="line">107</div><div class="line">108</div><div class="line">109</div><div class="line">110</div><div class="line">111</div><div class="line">112</div><div class="line">113</div><div class="line">114</div><div class="line">115</div><div class="line">116</div><div class="line">117</div><div class="line">118</div><div class="line">119</div><div class="line">120</div><div class="line">121</div><div class="line">122</div><div class="line">123</div><div class="line">124</div><div class="line">125</div><div class="line">126</div><div class="line">127</div><div class="line">128</div><div class="line">129</div><div class="line">130</div><div class="line">131</div><div class="line">132</div><div class="line">133</div><div class="line">134</div><div class="line">135</div><div class="line">136</div><div class="line">137</div><div class="line">138</div><div class="line">139</div><div class="line">140</div><div class="line">141</div><div class="line">142</div><div class="line">143</div><div class="line">144</div><div class="line">145</div><div class="line">146</div><div class="line">147</div><div class="line">148</div><div class="line">149</div><div class="line">150</div><div class="line">151</div><div class="line">152</div><div class="line">153</div><div class="line">154</div><div class="line">155</div><div class="line">156</div><div class="line">157</div><div class="line">158</div><div class="line">159</div><div class="line">160</div><div class="line">161</div><div class="line">162</div><div class="line">163</div><div class="line">164</div><div class="line">165</div><div class="line">166</div><div class="line">167</div><div class="line">168</div><div class="line">169</div><div class="line">170</div><div class="line">171</div><div class="line">172</div><div class="line">173</div><div class="line">174</div><div class="line">175</div><div class="line">176</div><div class="line">177</div><div class="line">178</div><div class="line">179</div><div class="line">180</div><div class="line">181</div><div class="line">182</div><div class="line">183</div><div class="line">184</div><div class="line">185</div><div class="line">186</div><div class="line">187</div><div class="line">188</div><div class="line">189</div><div class="line">190</div><div class="line">191</div><div class="line">192</div><div class="line">193</div><div class="line">194</div><div class="line">195</div><div class="line">196</div><div class="line">197</div><div class="line">198</div><div class="line">199</div><div class="line">200</div><div class="line">201</div><div class="line">202</div><div class="line">203</div><div class="line">204</div><div class="line">205</div><div class="line">206</div><div class="line">207</div><div class="line">208</div><div class="line">209</div><div class="line">210</div><div class="line">211</div><div class="line">212</div><div class="line">213</div><div class="line">214</div><div class="line">215</div><div class="line">216</div><div class="line">217</div><div class="line">218</div><div class="line">219</div><div class="line">220</div><div class="line">221</div><div class="line">222</div><div class="line">223</div><div class="line">224</div><div class="line">225</div><div class="line">226</div><div class="line">227</div><div class="line">228</div><div class="line">229</div><div class="line">230</div><div class="line">231</div><div class="line">232</div><div class="line">233</div><div class="line">234</div><div class="line">235</div><div class="line">236</div><div class="line">237</div><div class="line">238</div><div class="line">239</div><div class="line">240</div><div class="line">241</div><div class="line">242</div><div class="line">243</div><div class="line">244</div><div class="line">245</div><div class="line">246</div><div class="line">247</div><div class="line">248</div><div class="line">249</div><div class="line">250</div><div class="line">251</div><div class="line">252</div><div class="line">253</div><div class="line">254</div><div class="line">255</div><div class="line">256</div><div class="line">257</div><div class="line">258</div><div class="line">259</div><div class="line">260</div><div class="line">261</div><div class="line">262</div><div class="line">263</div><div class="line">264</div><div class="line">265</div><div class="line">266</div><div class="line">267</div><div class="line">268</div><div class="line">269</div><div class="line">270</div><div class="line">271</div><div class="line">272</div><div class="line">273</div><div class="line">274</div><div class="line">275</div><div class="line">276</div><div class="line">277</div><div class="line">278</div><div class="line">279</div><div class="line">280</div><div class="line">281</div><div class="line">282</div><div class="line">283</div><div class="line">284</div><div class="line">285</div><div class="line">286</div><div class="line">287</div><div class="line">288</div><div class="line">289</div><div class="line">290</div><div class="line">291</div><div class="line">292</div><div class="line">293</div><div class="line">294</div><div class="line">295</div><div class="line">296</div><div class="line">297</div><div class="line">298</div><div class="line">299</div><div class="line">300</div><div class="line">301</div><div class="line">302</div><div class="line">303</div><div class="line">304</div><div class="line">305</div><div class="line">306</div><div class="line">307</div><div class="line">308</div><div class="line">309</div><div class="line">310</div><div class="line">311</div><div class="line">312</div><div class="line">313</div><div class="line">314</div><div class="line">315</div><div class="line">316</div><div class="line">317</div><div class="line">318</div><div class="line">319</div><div class="line">320</div><div class="line">321</div><div class="line">322</div><div class="line">323</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">LRUAbstractMap</span> <span class="keyword">extends</span> <span class="title">java</span>.<span class="title">util</span>.<span class="title">AbstractMap</span> </span>&#123;</div><div class="line"></div><div class="line">    <span class="keyword">private</span> <span class="keyword">final</span> <span class="keyword">static</span> Logger LOGGER = LoggerFactory.getLogger(LRUAbstractMap.class);</div><div class="line"></div><div class="line">    <span class="comment">/**</span></div><div class="line">     * 检查是否超期线程</div><div class="line">     */</div><div class="line">    <span class="keyword">private</span> ExecutorService checkTimePool ;</div><div class="line"></div><div class="line">    <span class="comment">/**</span></div><div class="line">     * map 最大size</div><div class="line">     */</div><div class="line">    <span class="keyword">private</span> <span class="keyword">final</span> <span class="keyword">static</span> <span class="keyword">int</span> MAX_SIZE = <span class="number">1024</span> ;</div><div class="line"></div><div class="line">    <span class="keyword">private</span> <span class="keyword">final</span> <span class="keyword">static</span> ArrayBlockingQueue&lt;Node&gt; QUEUE = <span class="keyword">new</span> ArrayBlockingQueue&lt;&gt;(MAX_SIZE) ;</div><div class="line"></div><div class="line">    <span class="comment">/**</span></div><div class="line">     * 默认大小</div><div class="line">     */</div><div class="line">    <span class="keyword">private</span> <span class="keyword">final</span> <span class="keyword">static</span> <span class="keyword">int</span> DEFAULT_ARRAY_SIZE =<span class="number">1024</span> ;</div><div class="line"></div><div class="line"></div><div class="line">    <span class="comment">/**</span></div><div class="line">     * 数组长度</div><div class="line">     */</div><div class="line">    <span class="keyword">private</span> <span class="keyword">int</span> arraySize ;</div><div class="line"></div><div class="line">    <span class="comment">/**</span></div><div class="line">     * 数组</div><div class="line">     */</div><div class="line">    <span class="keyword">private</span> Object[] arrays ;</div><div class="line"></div><div class="line"></div><div class="line">    <span class="comment">/**</span></div><div class="line">     * 判断是否停止 flag</div><div class="line">     */</div><div class="line">    <span class="keyword">private</span> <span class="keyword">volatile</span> <span class="keyword">boolean</span> flag = <span class="keyword">true</span> ;</div><div class="line"></div><div class="line"></div><div class="line">    <span class="comment">/**</span></div><div class="line">     * 超时时间</div><div class="line">     */</div><div class="line">    <span class="keyword">private</span> <span class="keyword">final</span> <span class="keyword">static</span> Long EXPIRE_TIME = <span class="number">60</span> * <span class="number">60</span> * <span class="number">1000L</span> ;</div><div class="line"></div><div class="line">    <span class="comment">/**</span></div><div class="line">     * 整个 Map 的大小</div><div class="line">     */</div><div class="line">    <span class="keyword">private</span> <span class="keyword">volatile</span> AtomicInteger size  ;</div><div class="line"></div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="title">LRUAbstractMap</span><span class="params">()</span> </span>&#123;</div><div class="line"></div><div class="line"></div><div class="line">        arraySize = DEFAULT_ARRAY_SIZE;</div><div class="line">        arrays = <span class="keyword">new</span> Object[arraySize] ;</div><div class="line"></div><div class="line">        <span class="comment">//开启一个线程检查最先放入队列的值是否超期</span></div><div class="line">        executeCheckTime();</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="comment">/**</span></div><div class="line">     * 开启一个线程检查最先放入队列的值是否超期 设置为守护线程</div><div class="line">     */</div><div class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">executeCheckTime</span><span class="params">()</span> </span>&#123;</div><div class="line">        ThreadFactory namedThreadFactory = <span class="keyword">new</span> ThreadFactoryBuilder()</div><div class="line">                .setNameFormat(<span class="string">"check-thread-%d"</span>)</div><div class="line">                .setDaemon(<span class="keyword">true</span>)</div><div class="line">                .build();</div><div class="line">        checkTimePool = <span class="keyword">new</span> ThreadPoolExecutor(<span class="number">1</span>, <span class="number">1</span>, <span class="number">0L</span>, TimeUnit.MILLISECONDS,</div><div class="line">                <span class="keyword">new</span> ArrayBlockingQueue&lt;&gt;(<span class="number">1</span>),namedThreadFactory,<span class="keyword">new</span> ThreadPoolExecutor.AbortPolicy());</div><div class="line">        checkTimePool.execute(<span class="keyword">new</span> CheckTimeThread()) ;</div><div class="line"></div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="meta">@Override</span></div><div class="line">    <span class="function"><span class="keyword">public</span> Set&lt;Entry&gt; <span class="title">entrySet</span><span class="params">()</span> </span>&#123;</div><div class="line">        <span class="keyword">return</span> <span class="keyword">super</span>.keySet();</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="meta">@Override</span></div><div class="line">    <span class="function"><span class="keyword">public</span> Object <span class="title">put</span><span class="params">(Object key, Object value)</span> </span>&#123;</div><div class="line">        <span class="keyword">int</span> hash = hash(key);</div><div class="line">        <span class="keyword">int</span> index = hash % arraySize ;</div><div class="line">        Node currentNode = (Node) arrays[index] ;</div><div class="line"></div><div class="line">        <span class="keyword">if</span> (currentNode == <span class="keyword">null</span>)&#123;</div><div class="line">            arrays[index] = <span class="keyword">new</span> Node(<span class="keyword">null</span>,<span class="keyword">null</span>, key, value);</div><div class="line"></div><div class="line">            <span class="comment">//写入队列</span></div><div class="line">            QUEUE.offer((Node) arrays[index]) ;</div><div class="line"></div><div class="line">            sizeUp();</div><div class="line">        &#125;<span class="keyword">else</span> &#123;</div><div class="line">            Node cNode = currentNode ;</div><div class="line">            Node nNode = cNode ;</div><div class="line"></div><div class="line">            <span class="comment">//存在就覆盖</span></div><div class="line">            <span class="keyword">if</span> (nNode.key == key)&#123;</div><div class="line">                cNode.val = value ;</div><div class="line">            &#125;</div><div class="line"></div><div class="line">            <span class="keyword">while</span> (nNode.next != <span class="keyword">null</span>)&#123;</div><div class="line">                <span class="comment">//key 存在 就覆盖 简单判断</span></div><div class="line">                <span class="keyword">if</span> (nNode.key == key)&#123;</div><div class="line">                    nNode.val = value ;</div><div class="line">                    <span class="keyword">break</span> ;</div><div class="line">                &#125;<span class="keyword">else</span> &#123;</div><div class="line">                    <span class="comment">//不存在就新增链表</span></div><div class="line">                    sizeUp();</div><div class="line">                    Node node = <span class="keyword">new</span> Node(nNode,<span class="keyword">null</span>,key,value) ;</div><div class="line"></div><div class="line">                    <span class="comment">//写入队列</span></div><div class="line">                    QUEUE.offer(currentNode) ;</div><div class="line"></div><div class="line">                    cNode.next = node ;</div><div class="line">                &#125;</div><div class="line"></div><div class="line">                nNode = nNode.next ;</div><div class="line">            &#125;</div><div class="line"></div><div class="line">        &#125;</div><div class="line"></div><div class="line">        <span class="keyword">return</span> <span class="keyword">null</span> ;</div><div class="line">    &#125;</div><div class="line"></div><div class="line"></div><div class="line">    <span class="meta">@Override</span></div><div class="line">    <span class="function"><span class="keyword">public</span> Object <span class="title">get</span><span class="params">(Object key)</span> </span>&#123;</div><div class="line"></div><div class="line">        <span class="keyword">int</span> hash = hash(key) ;</div><div class="line">        <span class="keyword">int</span> index = hash % arraySize ;</div><div class="line">        Node currentNode = (Node) arrays[index] ;</div><div class="line"></div><div class="line">        <span class="keyword">if</span> (currentNode == <span class="keyword">null</span>)&#123;</div><div class="line">            <span class="keyword">return</span> <span class="keyword">null</span> ;</div><div class="line">        &#125;</div><div class="line">        <span class="keyword">if</span> (currentNode.next == <span class="keyword">null</span>)&#123;</div><div class="line"></div><div class="line">            <span class="comment">//更新时间</span></div><div class="line">            currentNode.setUpdateTime(System.currentTimeMillis());</div><div class="line"></div><div class="line">            <span class="comment">//没有冲突</span></div><div class="line">            <span class="keyword">return</span> currentNode ;</div><div class="line"></div><div class="line">        &#125;</div><div class="line"></div><div class="line">        Node nNode = currentNode ;</div><div class="line">        <span class="keyword">while</span> (nNode.next != <span class="keyword">null</span>)&#123;</div><div class="line"></div><div class="line">            <span class="keyword">if</span> (nNode.key == key)&#123;</div><div class="line"></div><div class="line">                <span class="comment">//更新时间</span></div><div class="line">                currentNode.setUpdateTime(System.currentTimeMillis());</div><div class="line"></div><div class="line">                <span class="keyword">return</span> nNode ;</div><div class="line">            &#125;</div><div class="line"></div><div class="line">            nNode = nNode.next ;</div><div class="line">        &#125;</div><div class="line"></div><div class="line">        <span class="keyword">return</span> <span class="keyword">super</span>.get(key);</div><div class="line">    &#125;</div><div class="line"></div><div class="line"></div><div class="line">    <span class="meta">@Override</span></div><div class="line">    <span class="function"><span class="keyword">public</span> Object <span class="title">remove</span><span class="params">(Object key)</span> </span>&#123;</div><div class="line"></div><div class="line">        <span class="keyword">int</span> hash = hash(key) ;</div><div class="line">        <span class="keyword">int</span> index = hash % arraySize ;</div><div class="line">        Node currentNode = (Node) arrays[index] ;</div><div class="line"></div><div class="line">        <span class="keyword">if</span> (currentNode == <span class="keyword">null</span>)&#123;</div><div class="line">            <span class="keyword">return</span> <span class="keyword">null</span> ;</div><div class="line">        &#125;</div><div class="line"></div><div class="line">        <span class="keyword">if</span> (currentNode.key == key)&#123;</div><div class="line">            sizeDown();</div><div class="line">            arrays[index] = <span class="keyword">null</span> ;</div><div class="line"></div><div class="line">            <span class="comment">//移除队列</span></div><div class="line">            QUEUE.poll();</div><div class="line">            <span class="keyword">return</span> currentNode ;</div><div class="line">        &#125;</div><div class="line"></div><div class="line">        Node nNode = currentNode ;</div><div class="line">        <span class="keyword">while</span> (nNode.next != <span class="keyword">null</span>)&#123;</div><div class="line"></div><div class="line">            <span class="keyword">if</span> (nNode.key == key)&#123;</div><div class="line">                sizeDown();</div><div class="line">                <span class="comment">//在链表中找到了 把上一个节点的 next 指向当前节点的下一个节点</span></div><div class="line">                nNode.pre.next = nNode.next ;</div><div class="line">                nNode = <span class="keyword">null</span> ;</div><div class="line"></div><div class="line">                <span class="comment">//移除队列</span></div><div class="line">                QUEUE.poll();</div><div class="line"></div><div class="line">                <span class="keyword">return</span> nNode;</div><div class="line">            &#125;</div><div class="line"></div><div class="line">            nNode = nNode.next ;</div><div class="line">        &#125;</div><div class="line"></div><div class="line">        <span class="keyword">return</span> <span class="keyword">super</span>.remove(key);</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="comment">/**</span></div><div class="line">     * 增加size</div><div class="line">     */</div><div class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">sizeUp</span><span class="params">()</span></span>&#123;</div><div class="line"></div><div class="line">        <span class="comment">//在put值时候认为里边已经有数据了</span></div><div class="line">        flag = <span class="keyword">true</span> ;</div><div class="line"></div><div class="line">        <span class="keyword">if</span> (size == <span class="keyword">null</span>)&#123;</div><div class="line">            size = <span class="keyword">new</span> AtomicInteger() ;</div><div class="line">        &#125;</div><div class="line">        <span class="keyword">int</span> size = <span class="keyword">this</span>.size.incrementAndGet();</div><div class="line">        <span class="keyword">if</span> (size &gt;= MAX_SIZE) &#123;</div><div class="line">            <span class="comment">//找到队列头的数据</span></div><div class="line">            Node node = QUEUE.poll() ;</div><div class="line">            <span class="keyword">if</span> (node == <span class="keyword">null</span>)&#123;</div><div class="line">                <span class="keyword">throw</span> <span class="keyword">new</span> RuntimeException(<span class="string">"data error"</span>) ;</div><div class="line">            &#125;</div><div class="line"></div><div class="line">            <span class="comment">//移除该 key</span></div><div class="line">            Object key = node.key ;</div><div class="line">            remove(key) ;</div><div class="line">            lruCallback() ;</div><div class="line">        &#125;</div><div class="line"></div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="comment">/**</span></div><div class="line">     * 数量减小</div><div class="line">     */</div><div class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">sizeDown</span><span class="params">()</span></span>&#123;</div><div class="line"></div><div class="line">        <span class="keyword">if</span> (QUEUE.size() == <span class="number">0</span>)&#123;</div><div class="line">            flag = <span class="keyword">false</span> ;</div><div class="line">        &#125;</div><div class="line"></div><div class="line">        <span class="keyword">this</span>.size.decrementAndGet() ;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="meta">@Override</span></div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">size</span><span class="params">()</span> </span>&#123;</div><div class="line">        <span class="keyword">return</span> size.get() ;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="comment">/**</span></div><div class="line">     * 链表</div><div class="line">     */</div><div class="line">    <span class="keyword">private</span> <span class="class"><span class="keyword">class</span> <span class="title">Node</span></span>&#123;</div><div class="line">        <span class="keyword">private</span> Node next ;</div><div class="line">        <span class="keyword">private</span> Node pre ;</div><div class="line">        <span class="keyword">private</span> Object key ;</div><div class="line">        <span class="keyword">private</span> Object val ;</div><div class="line">        <span class="keyword">private</span> Long updateTime ;</div><div class="line"></div><div class="line">        <span class="function"><span class="keyword">public</span> <span class="title">Node</span><span class="params">(Node pre,Node next, Object key, Object val)</span> </span>&#123;</div><div class="line">            <span class="keyword">this</span>.pre = pre ;</div><div class="line">            <span class="keyword">this</span>.next = next;</div><div class="line">            <span class="keyword">this</span>.key = key;</div><div class="line">            <span class="keyword">this</span>.val = val;</div><div class="line">            <span class="keyword">this</span>.updateTime = System.currentTimeMillis() ;</div><div class="line">        &#125;</div><div class="line"></div><div class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">setUpdateTime</span><span class="params">(Long updateTime)</span> </span>&#123;</div><div class="line">            <span class="keyword">this</span>.updateTime = updateTime;</div><div class="line">        &#125;</div><div class="line"></div><div class="line">        <span class="function"><span class="keyword">public</span> Long <span class="title">getUpdateTime</span><span class="params">()</span> </span>&#123;</div><div class="line">            <span class="keyword">return</span> updateTime;</div><div class="line">        &#125;</div><div class="line"></div><div class="line">        <span class="meta">@Override</span></div><div class="line">        <span class="function"><span class="keyword">public</span> String <span class="title">toString</span><span class="params">()</span> </span>&#123;</div><div class="line">            <span class="keyword">return</span> <span class="string">"Node&#123;"</span> +</div><div class="line">                    <span class="string">"key="</span> + key +</div><div class="line">                    <span class="string">", val="</span> + val +</div><div class="line">                    <span class="string">'&#125;'</span>;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line"></div><div class="line"></div><div class="line">    <span class="comment">/**</span></div><div class="line">     * copy HashMap 的 hash 实现</div><div class="line">     * <span class="doctag">@param</span> key</div><div class="line">     * <span class="doctag">@return</span></div><div class="line">     */</div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">hash</span><span class="params">(Object key)</span> </span>&#123;</div><div class="line">        <span class="keyword">int</span> h;</div><div class="line">        <span class="keyword">return</span> (key == <span class="keyword">null</span>) ? <span class="number">0</span> : (h = key.hashCode()) ^ (h &gt;&gt;&gt; <span class="number">16</span>);</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">lruCallback</span><span class="params">()</span></span>&#123;</div><div class="line">        LOGGER.debug(<span class="string">"lruCallback"</span>);</div><div class="line">    &#125;</div><div class="line"></div><div class="line"></div><div class="line">    <span class="keyword">private</span> <span class="class"><span class="keyword">class</span> <span class="title">CheckTimeThread</span> <span class="keyword">implements</span> <span class="title">Runnable</span></span>&#123;</div><div class="line"></div><div class="line">        <span class="meta">@Override</span></div><div class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">run</span><span class="params">()</span> </span>&#123;</div><div class="line">            <span class="keyword">while</span> (flag)&#123;</div><div class="line">                <span class="keyword">try</span> &#123;</div><div class="line">                    Node node = QUEUE.poll();</div><div class="line">                    <span class="keyword">if</span> (node == <span class="keyword">null</span>)&#123;</div><div class="line">                        <span class="keyword">continue</span> ;</div><div class="line">                    &#125;</div><div class="line">                    Long updateTime = node.getUpdateTime() ;</div><div class="line"></div><div class="line">                    <span class="keyword">if</span> ((updateTime - System.currentTimeMillis()) &gt;= EXPIRE_TIME)&#123;</div><div class="line">                        remove(node.key) ;</div><div class="line">                    &#125;</div><div class="line">                &#125; <span class="keyword">catch</span> (Exception e) &#123;</div><div class="line">                    LOGGER.error(<span class="string">"InterruptedException"</span>);</div><div class="line">                &#125;</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">&#125;</div></pre></td></tr></table></figure>
<p>感兴趣的朋友可以直接从:</p>
<p><a href="https://github.com/crossoverJie/Java-Interview/blob/master/src/main/java/com/crossoverjie/actual/LRUAbstractMap.java" target="_blank" rel="external">https://github.com/crossoverJie/Java-Interview/blob/master/src/main/java/com/crossoverjie/actual/LRUAbstractMap.java</a></p>
<p>下载代码本地运行。</p>
<p>代码看着比较多，其实实现的思路还是比较简单：</p>
<ul>
<li>采用了与 HashMap 一样的保存数据方式，只是自己手动实现了一个简易版。</li>
<li>内部采用了一个队列来保存每次写入的数据。</li>
<li>写入的时候判断缓存是否大于了阈值 N，如果满足则根据队列的 FIFO 特性将队列头的数据删除。因为队列头的数据肯定是最先放进去的。</li>
<li>再开启了一个守护线程用于判断最先放进去的数据是否超期（因为就算超期也是最先放进去的数据最有可能满足超期条件。）</li>
<li>设置为守护线程可以更好的表明其目的（最坏的情况下，如果是一个用户线程最终有可能导致程序不能正常退出，因为该线程一直在运行，守护线程则不会有这个情况。）</li>
</ul>
<p>以上代码大体功能满足了，但是有一个致命问题。</p>
<p>就是最近<strong>最少使用</strong>没有满足，删除的数据都是最先放入的数据。</p>
<blockquote>
<p>不过其中的 <code>put get</code> 流程算是一个简易的 HashMap 实现，可以对 HashMap 加深一些理解。</p>
</blockquote>
<h2 id="实现二"><a href="#实现二" class="headerlink" title="实现二"></a>实现二</h2><p>因此如何来实现一个完整的 LRU 缓存呢，这次不考虑过期时间的问题。</p>
<p>其实从上一个实现也能想到一些思路：</p>
<ul>
<li>要记录最近最少使用，那至少需要一个有序的集合来保证写入的顺序。</li>
<li>在使用了数据之后能够更新它的顺序。</li>
</ul>
<p>基于以上两点很容易想到一个常用的数据结构：<strong>链表</strong>。</p>
<ol>
<li>每次写入数据时将数据放入链表头结点。</li>
<li>使用数据时候将数据<strong>移动到头结点</strong>。</li>
<li>缓存数量超过阈值时移除链表尾部数据。</li>
</ol>
<p>因此有了以下实现：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div><div class="line">55</div><div class="line">56</div><div class="line">57</div><div class="line">58</div><div class="line">59</div><div class="line">60</div><div class="line">61</div><div class="line">62</div><div class="line">63</div><div class="line">64</div><div class="line">65</div><div class="line">66</div><div class="line">67</div><div class="line">68</div><div class="line">69</div><div class="line">70</div><div class="line">71</div><div class="line">72</div><div class="line">73</div><div class="line">74</div><div class="line">75</div><div class="line">76</div><div class="line">77</div><div class="line">78</div><div class="line">79</div><div class="line">80</div><div class="line">81</div><div class="line">82</div><div class="line">83</div><div class="line">84</div><div class="line">85</div><div class="line">86</div><div class="line">87</div><div class="line">88</div><div class="line">89</div><div class="line">90</div><div class="line">91</div><div class="line">92</div><div class="line">93</div><div class="line">94</div><div class="line">95</div><div class="line">96</div><div class="line">97</div><div class="line">98</div><div class="line">99</div><div class="line">100</div><div class="line">101</div><div class="line">102</div><div class="line">103</div><div class="line">104</div><div class="line">105</div><div class="line">106</div><div class="line">107</div><div class="line">108</div><div class="line">109</div><div class="line">110</div><div class="line">111</div><div class="line">112</div><div class="line">113</div><div class="line">114</div><div class="line">115</div><div class="line">116</div><div class="line">117</div><div class="line">118</div><div class="line">119</div><div class="line">120</div><div class="line">121</div><div class="line">122</div><div class="line">123</div><div class="line">124</div><div class="line">125</div><div class="line">126</div><div class="line">127</div><div class="line">128</div><div class="line">129</div><div class="line">130</div><div class="line">131</div><div class="line">132</div><div class="line">133</div><div class="line">134</div><div class="line">135</div><div class="line">136</div><div class="line">137</div><div class="line">138</div><div class="line">139</div><div class="line">140</div><div class="line">141</div><div class="line">142</div><div class="line">143</div><div class="line">144</div><div class="line">145</div><div class="line">146</div><div class="line">147</div><div class="line">148</div><div class="line">149</div><div class="line">150</div><div class="line">151</div><div class="line">152</div><div class="line">153</div><div class="line">154</div><div class="line">155</div><div class="line">156</div><div class="line">157</div><div class="line">158</div><div class="line">159</div><div class="line">160</div><div class="line">161</div><div class="line">162</div><div class="line">163</div><div class="line">164</div><div class="line">165</div><div class="line">166</div><div class="line">167</div><div class="line">168</div><div class="line">169</div><div class="line">170</div><div class="line">171</div><div class="line">172</div><div class="line">173</div><div class="line">174</div><div class="line">175</div><div class="line">176</div><div class="line">177</div><div class="line">178</div><div class="line">179</div><div class="line">180</div><div class="line">181</div><div class="line">182</div><div class="line">183</div><div class="line">184</div><div class="line">185</div><div class="line">186</div><div class="line">187</div><div class="line">188</div><div class="line">189</div><div class="line">190</div><div class="line">191</div><div class="line">192</div><div class="line">193</div><div class="line">194</div><div class="line">195</div><div class="line">196</div><div class="line">197</div><div class="line">198</div><div class="line">199</div><div class="line">200</div><div class="line">201</div><div class="line">202</div><div class="line">203</div><div class="line">204</div><div class="line">205</div><div class="line">206</div><div class="line">207</div><div class="line">208</div><div class="line">209</div><div class="line">210</div><div class="line">211</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">LRUMap</span>&lt;<span class="title">K</span>, <span class="title">V</span>&gt; </span>&#123;</div><div class="line">    <span class="keyword">private</span> <span class="keyword">final</span> Map&lt;K, V&gt; cacheMap = <span class="keyword">new</span> HashMap&lt;&gt;();</div><div class="line"></div><div class="line">    <span class="comment">/**</span></div><div class="line">     * 最大缓存大小</div><div class="line">     */</div><div class="line">    <span class="keyword">private</span> <span class="keyword">int</span> cacheSize;</div><div class="line"></div><div class="line">    <span class="comment">/**</span></div><div class="line">     * 节点大小</div><div class="line">     */</div><div class="line">    <span class="keyword">private</span> <span class="keyword">int</span> nodeCount;</div><div class="line"></div><div class="line"></div><div class="line">    <span class="comment">/**</span></div><div class="line">     * 头结点</div><div class="line">     */</div><div class="line">    <span class="keyword">private</span> Node&lt;K, V&gt; header;</div><div class="line"></div><div class="line">    <span class="comment">/**</span></div><div class="line">     * 尾结点</div><div class="line">     */</div><div class="line">    <span class="keyword">private</span> Node&lt;K, V&gt; tailer;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="title">LRUMap</span><span class="params">(<span class="keyword">int</span> cacheSize)</span> </span>&#123;</div><div class="line">        <span class="keyword">this</span>.cacheSize = cacheSize;</div><div class="line">        <span class="comment">//头结点的下一个结点为空</span></div><div class="line">        header = <span class="keyword">new</span> Node&lt;&gt;();</div><div class="line">        header.next = <span class="keyword">null</span>;</div><div class="line"></div><div class="line">        <span class="comment">//尾结点的上一个结点为空</span></div><div class="line">        tailer = <span class="keyword">new</span> Node&lt;&gt;();</div><div class="line">        tailer.tail = <span class="keyword">null</span>;</div><div class="line"></div><div class="line">        <span class="comment">//双向链表 头结点的上结点指向尾结点</span></div><div class="line">        header.tail = tailer;</div><div class="line"></div><div class="line">        <span class="comment">//尾结点的下结点指向头结点</span></div><div class="line">        tailer.next = header;</div><div class="line"></div><div class="line"></div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">put</span><span class="params">(K key, V value)</span> </span>&#123;</div><div class="line">        cacheMap.put(key, value);</div><div class="line"></div><div class="line">        <span class="comment">//双向链表中添加结点</span></div><div class="line">        addNode(key, value);</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">public</span> V <span class="title">get</span><span class="params">(K key)</span></span>&#123;</div><div class="line"></div><div class="line">        Node&lt;K, V&gt; node = getNode(key);</div><div class="line"></div><div class="line">        <span class="comment">//移动到头结点</span></div><div class="line">        moveToHead(node) ;</div><div class="line"></div><div class="line">        <span class="keyword">return</span> cacheMap.get(key);</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">moveToHead</span><span class="params">(Node&lt;K,V&gt; node)</span></span>&#123;</div><div class="line"></div><div class="line">        <span class="comment">//如果是最后的一个节点</span></div><div class="line">        <span class="keyword">if</span> (node.tail == <span class="keyword">null</span>)&#123;</div><div class="line">            node.next.tail = <span class="keyword">null</span> ;</div><div class="line">            tailer = node.next ;</div><div class="line">            nodeCount -- ;</div><div class="line">        &#125;</div><div class="line"></div><div class="line">        <span class="comment">//如果是本来就是头节点 不作处理</span></div><div class="line">        <span class="keyword">if</span> (node.next == <span class="keyword">null</span>)&#123;</div><div class="line">            <span class="keyword">return</span> ;</div><div class="line">        &#125;</div><div class="line"></div><div class="line">        <span class="comment">//如果处于中间节点</span></div><div class="line">        <span class="keyword">if</span> (node.tail != <span class="keyword">null</span> &amp;&amp; node.next != <span class="keyword">null</span>)&#123;</div><div class="line">            <span class="comment">//它的上一节点指向它的下一节点 也就删除当前节点</span></div><div class="line">            node.tail.next = node.next ;</div><div class="line">            nodeCount -- ;</div><div class="line">        &#125;</div><div class="line"></div><div class="line">        <span class="comment">//最后在头部增加当前节点</span></div><div class="line">        <span class="comment">//注意这里需要重新 new 一个对象，不然原本的node 还有着下面的引用，会造成内存溢出。</span></div><div class="line">        node = <span class="keyword">new</span> Node&lt;&gt;(node.getKey(),node.getValue()) ;</div><div class="line">        addHead(node) ;</div><div class="line"></div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="comment">/**</span></div><div class="line">     * 链表查询 效率较低</div><div class="line">     * <span class="doctag">@param</span> key</div><div class="line">     * <span class="doctag">@return</span></div><div class="line">     */</div><div class="line">    <span class="function"><span class="keyword">private</span> Node&lt;K,V&gt; <span class="title">getNode</span><span class="params">(K key)</span></span>&#123;</div><div class="line">        Node&lt;K,V&gt; node = tailer ;</div><div class="line">        <span class="keyword">while</span> (node != <span class="keyword">null</span>)&#123;</div><div class="line"></div><div class="line">            <span class="keyword">if</span> (node.getKey().equals(key))&#123;</div><div class="line">                <span class="keyword">return</span> node ;</div><div class="line">            &#125;</div><div class="line"></div><div class="line">            node = node.next ;</div><div class="line">        &#125;</div><div class="line"></div><div class="line">        <span class="keyword">return</span> <span class="keyword">null</span> ;</div><div class="line">    &#125;</div><div class="line"></div><div class="line"></div><div class="line">    <span class="comment">/**</span></div><div class="line">     * 写入头结点</div><div class="line">     * <span class="doctag">@param</span> key</div><div class="line">     * <span class="doctag">@param</span> value</div><div class="line">     */</div><div class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">addNode</span><span class="params">(K key, V value)</span> </span>&#123;</div><div class="line"></div><div class="line">        Node&lt;K, V&gt; node = <span class="keyword">new</span> Node&lt;&gt;(key, value);</div><div class="line"></div><div class="line">        <span class="comment">//容量满了删除最后一个</span></div><div class="line">        <span class="keyword">if</span> (cacheSize == nodeCount) &#123;</div><div class="line">            <span class="comment">//删除尾结点</span></div><div class="line">            delTail();</div><div class="line">        &#125;</div><div class="line"></div><div class="line">        <span class="comment">//写入头结点</span></div><div class="line">        addHead(node);</div><div class="line"></div><div class="line">    &#125;</div><div class="line"></div><div class="line"></div><div class="line"></div><div class="line">    <span class="comment">/**</span></div><div class="line">     * 添加头结点</div><div class="line">     *</div><div class="line">     * <span class="doctag">@param</span> node</div><div class="line">     */</div><div class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">addHead</span><span class="params">(Node&lt;K, V&gt; node)</span> </span>&#123;</div><div class="line"></div><div class="line">        <span class="comment">//写入头结点</span></div><div class="line">        header.next = node;</div><div class="line">        node.tail = header;</div><div class="line">        header = node;</div><div class="line">        nodeCount++;</div><div class="line"></div><div class="line">        <span class="comment">//如果写入的数据大于2个 就将初始化的头尾结点删除</span></div><div class="line">        <span class="keyword">if</span> (nodeCount == <span class="number">2</span>) &#123;</div><div class="line">            tailer.next.next.tail = <span class="keyword">null</span>;</div><div class="line">            tailer = tailer.next.next;</div><div class="line">        &#125;</div><div class="line"></div><div class="line">    &#125;    </div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">delTail</span><span class="params">()</span> </span>&#123;</div><div class="line">        <span class="comment">//把尾结点从缓存中删除</span></div><div class="line">        cacheMap.remove(tailer.getKey());</div><div class="line"></div><div class="line">        <span class="comment">//删除尾结点</span></div><div class="line">        tailer.next.tail = <span class="keyword">null</span>;</div><div class="line">        tailer = tailer.next;</div><div class="line"></div><div class="line">        nodeCount--;</div><div class="line"></div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="keyword">private</span> <span class="class"><span class="keyword">class</span> <span class="title">Node</span>&lt;<span class="title">K</span>, <span class="title">V</span>&gt; </span>&#123;</div><div class="line">        <span class="keyword">private</span> K key;</div><div class="line">        <span class="keyword">private</span> V value;</div><div class="line">        Node&lt;K, V&gt; tail;</div><div class="line">        Node&lt;K, V&gt; next;</div><div class="line"></div><div class="line">        <span class="function"><span class="keyword">public</span> <span class="title">Node</span><span class="params">(K key, V value)</span> </span>&#123;</div><div class="line">            <span class="keyword">this</span>.key = key;</div><div class="line">            <span class="keyword">this</span>.value = value;</div><div class="line">        &#125;</div><div class="line"></div><div class="line">        <span class="function"><span class="keyword">public</span> <span class="title">Node</span><span class="params">()</span> </span>&#123;</div><div class="line">        &#125;</div><div class="line"></div><div class="line">        <span class="function"><span class="keyword">public</span> K <span class="title">getKey</span><span class="params">()</span> </span>&#123;</div><div class="line">            <span class="keyword">return</span> key;</div><div class="line">        &#125;</div><div class="line"></div><div class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">setKey</span><span class="params">(K key)</span> </span>&#123;</div><div class="line">            <span class="keyword">this</span>.key = key;</div><div class="line">        &#125;</div><div class="line"></div><div class="line">        <span class="function"><span class="keyword">public</span> V <span class="title">getValue</span><span class="params">()</span> </span>&#123;</div><div class="line">            <span class="keyword">return</span> value;</div><div class="line">        &#125;</div><div class="line"></div><div class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">setValue</span><span class="params">(V value)</span> </span>&#123;</div><div class="line">            <span class="keyword">this</span>.value = value;</div><div class="line">        &#125;</div><div class="line"></div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="meta">@Override</span></div><div class="line">    <span class="function"><span class="keyword">public</span> String <span class="title">toString</span><span class="params">()</span> </span>&#123;</div><div class="line">        StringBuilder sb = <span class="keyword">new</span> StringBuilder() ;</div><div class="line">        Node&lt;K,V&gt; node = tailer ;</div><div class="line">        <span class="keyword">while</span> (node != <span class="keyword">null</span>)&#123;</div><div class="line">            sb.append(node.getKey()).append(<span class="string">":"</span>)</div><div class="line">                    .append(node.getValue())</div><div class="line">                    .append(<span class="string">"--&gt;"</span>) ;</div><div class="line"></div><div class="line">            node = node.next ;</div><div class="line">        &#125;</div><div class="line"></div><div class="line"></div><div class="line">        <span class="keyword">return</span> sb.toString();</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<p>源码：<br><a href="https://github.com/crossoverJie/Java-Interview/blob/master/src/main/java/com/crossoverjie/actual/LRUMap.java" target="_blank" rel="external">https://github.com/crossoverJie/Java-Interview/blob/master/src/main/java/com/crossoverjie/actual/LRUMap.java</a></p>
<p>实际效果，写入时：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div></pre></td><td class="code"><pre><div class="line">    <span class="meta">@Test</span></div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">put</span><span class="params">()</span> <span class="keyword">throws</span> Exception </span>&#123;</div><div class="line">        LRUMap&lt;String,Integer&gt; lruMap = <span class="keyword">new</span> LRUMap(<span class="number">3</span>) ;</div><div class="line">        lruMap.put(<span class="string">"1"</span>,<span class="number">1</span>) ;</div><div class="line">        lruMap.put(<span class="string">"2"</span>,<span class="number">2</span>) ;</div><div class="line">        lruMap.put(<span class="string">"3"</span>,<span class="number">3</span>) ;</div><div class="line"></div><div class="line">        System.out.println(lruMap.toString());</div><div class="line"></div><div class="line">        lruMap.put(<span class="string">"4"</span>,<span class="number">4</span>) ;</div><div class="line">        System.out.println(lruMap.toString());</div><div class="line"></div><div class="line">        lruMap.put(<span class="string">"5"</span>,<span class="number">5</span>) ;</div><div class="line">        System.out.println(lruMap.toString());</div><div class="line">    &#125;</div><div class="line"></div><div class="line"><span class="comment">//输出：</span></div><div class="line"><span class="number">1</span>:<span class="number">1</span>--&gt;<span class="number">2</span>:<span class="number">2</span>--&gt;<span class="number">3</span>:<span class="number">3</span>--&gt;</div><div class="line"><span class="number">2</span>:<span class="number">2</span>--&gt;<span class="number">3</span>:<span class="number">3</span>--&gt;<span class="number">4</span>:<span class="number">4</span>--&gt;</div><div class="line"><span class="number">3</span>:<span class="number">3</span>--&gt;<span class="number">4</span>:<span class="number">4</span>--&gt;<span class="number">5</span>:<span class="number">5</span>--&gt;</div></pre></td></tr></table></figure>
<p>使用时：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div></pre></td><td class="code"><pre><div class="line">    <span class="meta">@Test</span></div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">get</span><span class="params">()</span> <span class="keyword">throws</span> Exception </span>&#123;</div><div class="line">        LRUMap&lt;String,Integer&gt; lruMap = <span class="keyword">new</span> LRUMap(<span class="number">3</span>) ;</div><div class="line">        lruMap.put(<span class="string">"1"</span>,<span class="number">1</span>) ;</div><div class="line">        lruMap.put(<span class="string">"2"</span>,<span class="number">2</span>) ;</div><div class="line">        lruMap.put(<span class="string">"3"</span>,<span class="number">3</span>) ;</div><div class="line"></div><div class="line">        System.out.println(lruMap.toString());</div><div class="line">        System.out.println(<span class="string">"=============="</span>);</div><div class="line"></div><div class="line">        Integer integer = lruMap.get(<span class="string">"1"</span>);</div><div class="line">        System.out.println(integer);</div><div class="line">        System.out.println(<span class="string">"=============="</span>);</div><div class="line">        System.out.println(lruMap.toString());</div><div class="line">    &#125;</div><div class="line">    </div><div class="line"><span class="comment">//输出</span></div><div class="line"><span class="number">1</span>:<span class="number">1</span>--&gt;<span class="number">2</span>:<span class="number">2</span>--&gt;<span class="number">3</span>:<span class="number">3</span>--&gt;</div><div class="line">==============</div><div class="line"><span class="number">1</span></div><div class="line">==============</div><div class="line"><span class="number">2</span>:<span class="number">2</span>--&gt;<span class="number">3</span>:<span class="number">3</span>--&gt;<span class="number">1</span>:<span class="number">1</span>--&gt;</div></pre></td></tr></table></figure>
<p>实现思路和上文提到的一致，说下重点：</p>
<ul>
<li>数据是直接利用 HashMap 来存放的。</li>
<li>内部使用了一个双向链表来存放数据，所以有一个头结点 header，以及尾结点 tailer。</li>
<li>每次写入头结点，删除尾结点时都是依赖于 header tailer，如果看着比较懵建议自己实现一个链表熟悉下，或结合下文的对象关系图一起理解。</li>
<li>使用数据移动到链表头时，第一步是需要在双向链表中找到该节点。这里就体现出链表的问题了。查找效率很低，最差需要 <code>O(N)</code>。之后依赖于当前节点进行移动。</li>
<li>在写入头结点时有判断链表大小等于 2 时需要删除初始化的头尾结点。这是因为初始化时候生成了两个双向节点，没有数据只是为了形成一个数据结构。当真实数据进来之后需要删除以方便后续的操作（这点可以继续优化）。</li>
<li>以上的所有操作都是线程不安全的，需要使用者自行控制。</li>
</ul>
<p>下面是对象关系图：</p>
<h3 id="初始化时"><a href="#初始化时" class="headerlink" title="初始化时"></a>初始化时</h3><p><img src="https://i.loli.net/2019/05/08/5cd1d7b842ebd.jpg" alt=""></p>
<h3 id="写入数据时"><a href="#写入数据时" class="headerlink" title="写入数据时"></a>写入数据时</h3><figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div></pre></td><td class="code"><pre><div class="line">LRUMap&lt;String,Integer&gt; lruMap = <span class="keyword">new</span> LRUMap(<span class="number">3</span>) ;</div><div class="line">lruMap.put(<span class="string">"1"</span>,<span class="number">1</span>) ;</div></pre></td></tr></table></figure>
<p><img src="https://i.loli.net/2019/05/08/5cd1d7bace008.jpg" alt=""></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div></pre></td><td class="code"><pre><div class="line">lruMap.put(<span class="string">"2"</span>,<span class="number">2</span>) ;</div></pre></td></tr></table></figure>
<p><img src="https://i.loli.net/2019/05/08/5cd1d7bdae29e.jpg" alt=""></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div></pre></td><td class="code"><pre><div class="line">lruMap.put(<span class="string">"3"</span>,<span class="number">3</span>) ;</div></pre></td></tr></table></figure>
<p><img src="https://i.loli.net/2019/05/08/5cd1d7bf974c6.jpg" alt=""></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div></pre></td><td class="code"><pre><div class="line">lruMap.put(<span class="string">"4"</span>,<span class="number">4</span>) ;</div></pre></td></tr></table></figure>
<p><img src="https://i.loli.net/2019/05/08/5cd1d7c26fee5.jpg" alt=""></p>
<h3 id="获取数据时"><a href="#获取数据时" class="headerlink" title="获取数据时"></a>获取数据时</h3><p>数据和上文一样：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div></pre></td><td class="code"><pre><div class="line">Integer integer = lruMap.get(<span class="string">"2"</span>);</div></pre></td></tr></table></figure>
<p><img src="https://i.loli.net/2019/05/08/5cd1d7c54a763.jpg" alt=""></p>
<p>通过以上几张图应该是很好理解数据是如何存放的了。</p>
<h2 id="实现三"><a href="#实现三" class="headerlink" title="实现三"></a>实现三</h2><p>其实如果对 Java 的集合比较熟悉的话，会发现上文的结构和 LinkedHashMap 非常类似。</p>
<p>对此不太熟悉的朋友可以先了解下 <a href="http://crossoverjie.top/2018/02/06/LinkedHashMap/">LinkedHashMap 底层分析</a> 。</p>
<p>所以我们完全可以借助于它来实现：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div></pre></td><td class="code"><pre><div class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">LRULinkedMap</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt; </span>&#123;</div><div class="line"></div><div class="line"></div><div class="line">    <span class="comment">/**</span></div><div class="line">     * 最大缓存大小</div><div class="line">     */</div><div class="line">    <span class="keyword">private</span> <span class="keyword">int</span> cacheSize;</div><div class="line"></div><div class="line">    <span class="keyword">private</span> LinkedHashMap&lt;K,V&gt; cacheMap ;</div><div class="line"></div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="title">LRULinkedMap</span><span class="params">(<span class="keyword">int</span> cacheSize)</span> </span>&#123;</div><div class="line">        <span class="keyword">this</span>.cacheSize = cacheSize;</div><div class="line"></div><div class="line">        cacheMap = <span class="keyword">new</span> LinkedHashMap(<span class="number">16</span>,<span class="number">0.75F</span>,<span class="keyword">true</span>)&#123;</div><div class="line">            <span class="meta">@Override</span></div><div class="line">            <span class="function"><span class="keyword">protected</span> <span class="keyword">boolean</span> <span class="title">removeEldestEntry</span><span class="params">(Map.Entry eldest)</span> </span>&#123;</div><div class="line">                <span class="keyword">if</span> (cacheSize + <span class="number">1</span> == cacheMap.size())&#123;</div><div class="line">                    <span class="keyword">return</span> <span class="keyword">true</span> ;</div><div class="line">                &#125;<span class="keyword">else</span> &#123;</div><div class="line">                    <span class="keyword">return</span> <span class="keyword">false</span> ;</div><div class="line">                &#125;</div><div class="line">            &#125;</div><div class="line">        &#125;;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">put</span><span class="params">(K key,V value)</span></span>&#123;</div><div class="line">        cacheMap.put(key,value) ;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">public</span> V <span class="title">get</span><span class="params">(K key)</span></span>&#123;</div><div class="line">        <span class="keyword">return</span> cacheMap.get(key) ;</div><div class="line">    &#125;</div><div class="line"></div><div class="line"></div><div class="line">    <span class="keyword">public</span> Collection&lt;Map.Entry&lt;K, V&gt;&gt; getAll() &#123;</div><div class="line">        <span class="keyword">return</span> <span class="keyword">new</span> ArrayList&lt;Map.Entry&lt;K, V&gt;&gt;(cacheMap.entrySet());</div><div class="line">    &#125;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<p>源码：<br><a href="https://github.com/crossoverJie/Java-Interview/blob/master/src/main/java/com/crossoverjie/actual/LRULinkedMap.java" target="_blank" rel="external">https://github.com/crossoverJie/Java-Interview/blob/master/src/main/java/com/crossoverjie/actual/LRULinkedMap.java</a></p>
<p>这次就比较简洁了，也就几行代码（具体的逻辑 LinkedHashMap 已经帮我们实现好了）</p>
<p>实际效果:</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div></pre></td><td class="code"><pre><div class="line">    <span class="meta">@Test</span></div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">put</span><span class="params">()</span> <span class="keyword">throws</span> Exception </span>&#123;</div><div class="line">        LRULinkedMap&lt;String,Integer&gt; map = <span class="keyword">new</span> LRULinkedMap(<span class="number">3</span>) ;</div><div class="line">        map.put(<span class="string">"1"</span>,<span class="number">1</span>);</div><div class="line">        map.put(<span class="string">"2"</span>,<span class="number">2</span>);</div><div class="line">        map.put(<span class="string">"3"</span>,<span class="number">3</span>);</div><div class="line"></div><div class="line">        <span class="keyword">for</span> (Map.Entry&lt;String, Integer&gt; e : map.getAll())&#123;</div><div class="line">            System.out.print(e.getKey() + <span class="string">" : "</span> + e.getValue() + <span class="string">"\t"</span>);</div><div class="line">        &#125;</div><div class="line"></div><div class="line">        System.out.println(<span class="string">""</span>);</div><div class="line">        map.put(<span class="string">"4"</span>,<span class="number">4</span>);</div><div class="line">        <span class="keyword">for</span> (Map.Entry&lt;String, Integer&gt; e : map.getAll())&#123;</div><div class="line">            System.out.print(e.getKey() + <span class="string">" : "</span> + e.getValue() + <span class="string">"\t"</span>);</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    </div><div class="line"><span class="comment">//输出</span></div><div class="line"><span class="number">1</span> : <span class="number">1</span>	<span class="number">2</span> : <span class="number">2</span>	<span class="number">3</span> : <span class="number">3</span>	</div><div class="line"><span class="number">2</span> : <span class="number">2</span>	<span class="number">3</span> : <span class="number">3</span>	<span class="number">4</span> : <span class="number">4</span></div></pre></td></tr></table></figure>
<p>使用时：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div></pre></td><td class="code"><pre><div class="line">    <span class="meta">@Test</span></div><div class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">get</span><span class="params">()</span> <span class="keyword">throws</span> Exception </span>&#123;</div><div class="line">        LRULinkedMap&lt;String,Integer&gt; map = <span class="keyword">new</span> LRULinkedMap(<span class="number">4</span>) ;</div><div class="line">        map.put(<span class="string">"1"</span>,<span class="number">1</span>);</div><div class="line">        map.put(<span class="string">"2"</span>,<span class="number">2</span>);</div><div class="line">        map.put(<span class="string">"3"</span>,<span class="number">3</span>);</div><div class="line">        map.put(<span class="string">"4"</span>,<span class="number">4</span>);</div><div class="line"></div><div class="line">        <span class="keyword">for</span> (Map.Entry&lt;String, Integer&gt; e : map.getAll())&#123;</div><div class="line">            System.out.print(e.getKey() + <span class="string">" : "</span> + e.getValue() + <span class="string">"\t"</span>);</div><div class="line">        &#125;</div><div class="line"></div><div class="line">        System.out.println(<span class="string">""</span>);</div><div class="line">        map.get(<span class="string">"1"</span>) ;</div><div class="line">        <span class="keyword">for</span> (Map.Entry&lt;String, Integer&gt; e : map.getAll())&#123;</div><div class="line">            System.out.print(e.getKey() + <span class="string">" : "</span> + e.getValue() + <span class="string">"\t"</span>);</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="comment">//输出</span></div><div class="line"><span class="number">1</span> : <span class="number">1</span>	<span class="number">2</span> : <span class="number">2</span>	<span class="number">3</span> : <span class="number">3</span>	<span class="number">4</span> : <span class="number">4</span>	</div><div class="line"><span class="number">2</span> : <span class="number">2</span>	<span class="number">3</span> : <span class="number">3</span>	<span class="number">4</span> : <span class="number">4</span>	<span class="number">1</span> : <span class="number">1</span></div></pre></td></tr></table></figure>
<p>LinkedHashMap 内部也有维护一个双向队列，在初始化时也会给定一个缓存大小的阈值。初始化时自定义是否需要删除最近不常使用的数据，如果是则会按照实现二中的方式管理数据。</p>
<p>其实主要代码就是重写了 LinkedHashMap 的 removeEldestEntry 方法:</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div></pre></td><td class="code"><pre><div class="line"><span class="function"><span class="keyword">protected</span> <span class="keyword">boolean</span> <span class="title">removeEldestEntry</span><span class="params">(Map.Entry&lt;K,V&gt; eldest)</span> </span>&#123;</div><div class="line">    <span class="keyword">return</span> <span class="keyword">false</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
<p>它默认是返回 false，也就是不会管有没有超过阈值。</p>
<p>所以我们自定义大于了阈值时返回 true，这样 LinkedHashMap 就会帮我们删除最近最少使用的数据。</p>
<h2 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h2><p>以上就是对 LRU 缓存的实现，了解了这些至少在平时使用时可以知其所以然。</p>
<p>当然业界使用较多的还有 <a href="https://github.com/google/guava" target="_blank" rel="external">guava</a> 的实现，并且它还支持多种过期策略。</p>
<h2 id="号外"><a href="#号外" class="headerlink" title="号外"></a>号外</h2><p>最近在总结一些 Java 相关的知识点，感兴趣的朋友可以一起维护。</p>
<blockquote>
<p>地址: <a href="https://github.com/crossoverJie/Java-Interview" target="_blank" rel="external">https://github.com/crossoverJie/Java-Interview</a></p>
</blockquote>

      
    </div>

    <div>
      
        
<div id="wechat_subscriber" style="display: block； padding: 10px 0; margin: 20px auto; width: 100%; text-align: center">
    <img id="wechat_subscriber_qcode" src="/uploads/weixinfooter1.jpg" alt="crossoverJie wechat" style="width: 200px; max-width: 100%;"/>
    <div>我很有眼光！</div>
</div>

      
    </div>

    <div>
      
        
  <div style="padding: 10px 0; margin: 20px auto; width: 90%; text-align: center;">
    <div>请我吃🍗</div>
    <button id="rewardButton" disable="enable" onclick="var qr = document.getElementById('QR'); if (qr.style.display === 'none') {qr.style.display='block';} else {qr.style.display='none'}">
      <span>赏</span>
    </button>
    <div id="QR" style="display: none;">
      
        <div id="wechat" style="display: inline-block">
          <img id="wechat_qr" src="/weixin-reward-image.jpg" alt="crossoverJie WeChat Pay"/>
          <p>微信打赏</p>
        </div>
      
      
        <div id="alipay" style="display: inline-block">
          <img id="alipay_qr" src="/alipay-reward-image.jpg" alt="crossoverJie Alipay"/>
          <p>支付宝打赏</p>
        </div>
      
    </div>
  </div>


      
    </div>

    <footer class="post-footer">
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2018/03/29/distributed-lock/distributed-lock-redis/" rel="next" title="基于 Redis 的分布式锁">
                <i class="fa fa-chevron-left"></i> 基于 Redis 的分布式锁
              </a>
            
          </div>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2018/04/12/translation/translation-What Is The Best Programming Language to Start/" rel="prev" title="【译】对于初学者什么是最好的编程语言？">
                【译】对于初学者什么是最好的编程语言？ <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          

  <p>热评文章</p>
  <div class="ds-top-threads" data-range="weekly" data-num-items="4"></div>


          
  <div class="comments" id="comments">
    
      <div id="disqus_thread">
        <noscript>
          Please enable JavaScript to view the
          <a href="//disqus.com/?ref_noscript">comments powered by Disqus.</a>
        </noscript>
      </div>
    
  </div>


        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap" >
            Table of Contents
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview">
            Overview
          </li>
        </ul>
      

      <section class="site-overview sidebar-panel ">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
          <img class="site-author-image" itemprop="image"
               src="/uploads/crossoverjie.jpg"
               alt="crossoverJie" />
          <p class="site-author-name" itemprop="name">crossoverJie</p>
          <p class="site-description motion-element" itemprop="description">You never know what you can do till you try.</p>
        </div>
        <nav class="site-state motion-element">
          <div class="site-state-item site-state-posts">
            <a href="/archives">
              <span class="site-state-item-count">116</span>
              <span class="site-state-item-name">posts</span>
            </a>
          </div>

          
            <div class="site-state-item site-state-categories">
              <a href="/categories">
                <span class="site-state-item-count">45</span>
                <span class="site-state-item-name">categories</span>
              </a>
            </div>
          

          
            <div class="site-state-item site-state-tags">
              <a href="/tags">
                <span class="site-state-item-count">109</span>
                <span class="site-state-item-name">tags</span>
              </a>
            </div>
          

        </nav>

        
          <div class="feed-link motion-element">
            <a href="/atom.xml" rel="alternate">
              <i class="fa fa-rss"></i>
              RSS
            </a>
          </div>
        

        <div class="links-of-author motion-element">
          
            
              <span class="links-of-author-item">
                <a href="https://github.com/crossoverJie" target="_blank" title="GitHub">
                  
                    <i class="fa fa-fw fa-github"></i>
                  
                  GitHub
                </a>
              </span>
            
              <span class="links-of-author-item">
                <a href="http://www.jianshu.com/users/e2d07947c112/latest_articles" target="_blank" title="简书">
                  
                    <i class="fa fa-fw fa-book"></i>
                  
                  简书
                </a>
              </span>
            
              <span class="links-of-author-item">
                <a href="https://juejin.im/user/576d4aaf7db2a20054ea4544" target="_blank" title="掘金">
                  
                    <i class="fa fa-fw fa-bookmark"></i>
                  
                  掘金
                </a>
              </span>
            
              <span class="links-of-author-item">
                <a href="https://twitter.com/crossoverJie" target="_blank" title="Twitter">
                  
                    <i class="fa fa-fw fa-twitter"></i>
                  
                  Twitter
                </a>
              </span>
            
          
        </div>

        
        

        
        
          <div class="links-of-blogroll motion-element links-of-blogroll-inline">
            <div class="links-of-blogroll-title">
              <i class="fa  fa-fw fa-globe"></i>
              友情链接
            </div>
            <ul class="links-of-blogroll-list">
              
                <li class="links-of-blogroll-item">
                  <a href="http://wuchong.me" title="Jark's Blog" target="_blank">Jark's Blog</a>
                </li>
              
                <li class="links-of-blogroll-item">
                  <a href="http://tengj.top" title="嘟嘟独立博客" target="_blank">嘟嘟独立博客</a>
                </li>
              
                <li class="links-of-blogroll-item">
                  <a href="http://yemengying.com/" title="Giraffe Home" target="_blank">Giraffe Home</a>
                </li>
              
                <li class="links-of-blogroll-item">
                  <a href="https://blog.jamespan.me/" title="潘小鶸(ruò)" target="_blank">潘小鶸(ruò)</a>
                </li>
              
                <li class="links-of-blogroll-item">
                  <a href="http://fangjian0423.github.io/" title="Format's Notes" target="_blank">Format's Notes</a>
                </li>
              
                <li class="links-of-blogroll-item">
                  <a href="https://yuzhouwan.com/" title="Benedict Jin" target="_blank">Benedict Jin</a>
                </li>
              
                <li class="links-of-blogroll-item">
                  <a href="http://blog.didispace.com/" title="程序猿DD" target="_blank">程序猿DD</a>
                </li>
              
                <li class="links-of-blogroll-item">
                  <a href="https://blog.52itstyle.vip/" title="小柒博客" target="_blank">小柒博客</a>
                </li>
              
                <li class="links-of-blogroll-item">
                  <a href="http://cmsblogs.com/" title="Java技术驿站" target="_blank">Java技术驿站</a>
                </li>
              
                <li class="links-of-blogroll-item">
                  <a href="https://vim.ink/" title="vim 教程网" target="_blank">vim 教程网</a>
                </li>
              
                <li class="links-of-blogroll-item">
                  <a href="https://www.jitwxs.cn" title="jitwxs" target="_blank">jitwxs</a>
                </li>
              
                <li class="links-of-blogroll-item">
                  <a href="http://www.javaboy.org" title="江南一点雨" target="_blank">江南一点雨</a>
                </li>
              
                <li class="links-of-blogroll-item">
                  <a href="http://www.liangsonghua.me" title="松花皮蛋的黑板报" target="_blank">松花皮蛋的黑板报</a>
                </li>
              
                <li class="links-of-blogroll-item">
                  <a href="https://www.fi-ads.com" title="Future iDeal" target="_blank">Future iDeal</a>
                </li>
              
            </ul>
          </div>
        

      </section>

      
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">
            
              
            
            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#前言"><span class="nav-number">1.</span> <span class="nav-text">前言</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#实现一"><span class="nav-number">2.</span> <span class="nav-text">实现一</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#实现二"><span class="nav-number">3.</span> <span class="nav-text">实现二</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#初始化时"><span class="nav-number">3.1.</span> <span class="nav-text">初始化时</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#写入数据时"><span class="nav-number">3.2.</span> <span class="nav-text">写入数据时</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#获取数据时"><span class="nav-number">3.3.</span> <span class="nav-text">获取数据时</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#实现三"><span class="nav-number">4.</span> <span class="nav-text">实现三</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#总结"><span class="nav-number">5.</span> <span class="nav-text">总结</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#号外"><span class="nav-number">6.</span> <span class="nav-text">号外</span></a></li></ol></div>
            
          </div>
        </section>
      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright" >
  
  &copy;  2016 - 
  <span itemprop="copyrightYear">2019</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">crossoverJie</span>
</div>

<div class="powered-by">
  Powered by <a class="theme-link" href="http://hexo.io">Hexo</a>
</div>

<div class="theme-info">
  Theme -
  <a class="theme-link" href="https://github.com/iissnan/hexo-theme-next">
    NexT.Pisces
  </a>
</div>

        

<div class="busuanzi-count">

  <script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>

  
    <span class="site-uv"><i class="fa fa-user"></i><span class="busuanzi-value" id="busuanzi_value_site_uv"></span>人数</span>
  

  
    <span class="site-pv">您是第<span class="busuanzi-value" id="busuanzi_value_site_pv"></span>位童鞋</span>
  
  
</div>



        
      </div>
    </footer>

    <div class="back-to-top">
      <i class="fa fa-arrow-up"></i>
    </div>
  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  



  
  <script type="text/javascript" src="/vendors/jquery/index.js?v=2.1.3"></script>

  
  <script type="text/javascript" src="/vendors/fastclick/lib/fastclick.min.js?v=1.0.6"></script>

  
  <script type="text/javascript" src="/vendors/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>

  
  <script type="text/javascript" src="/vendors/velocity/velocity.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/vendors/velocity/velocity.ui.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/vendors/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.0.1"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.0.1"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.0.1"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.0.1"></script>



  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=5.0.1"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=5.0.1"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.0.1"></script>



  



  

    <script type="text/javascript">
      var disqus_shortname = 'crossoverjie';
      var disqus_identifier = '2018/04/07/algorithm/LRU-cache/';
      var disqus_title = "动手实现一个 LRU cache";
      var disqus_url = 'http://crossoverjie.top/2018/04/07/algorithm/LRU-cache/';

      function run_disqus_script(disqus_script){
        var dsq = document.createElement('script');
        dsq.type = 'text/javascript';
        dsq.async = true;
        dsq.src = '//' + disqus_shortname + '.disqus.com/' + disqus_script;
        (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
      }

      run_disqus_script('count.js');
      
        run_disqus_script('embed.js');
      
    </script>
  




  
  
  <script type="text/javascript">
    // Popup Window;
    var isfetched = false;
    // Search DB path;
    var search_path = "search.xml";
    if (search_path.length == 0) {
       search_path = "search.xml";
    }
    var path = "/" + search_path;
    // monitor main search box;

    function proceedsearch() {
      $("body").append('<div class="popoverlay">').css('overflow', 'hidden');
      $('.popup').toggle();

    }
    // search function;
    var searchFunc = function(path, search_id, content_id) {
    'use strict';
    $.ajax({
        url: path,
        dataType: "xml",
        async: true,
        success: function( xmlResponse ) {
            // get the contents from search data
            isfetched = true;
            $('.popup').detach().appendTo('.header-inner');
            var datas = $( "entry", xmlResponse ).map(function() {
                return {
                    title: $( "title", this ).text(),
                    content: $("content",this).text(),
                    url: $( "url" , this).text()
                };
            }).get();
            var $input = document.getElementById(search_id);
            var $resultContent = document.getElementById(content_id);
            $input.addEventListener('input', function(){
                var matchcounts = 0;
                var str='<ul class=\"search-result-list\">';                
                var keywords = this.value.trim().toLowerCase().split(/[\s\-]+/);
                $resultContent.innerHTML = "";
                if (this.value.trim().length > 1) {
                // perform local searching
                datas.forEach(function(data) {
                    var isMatch = true;
                    var content_index = [];
                    var data_title = data.title.trim().toLowerCase();
                    var data_content = data.content.trim().replace(/<[^>]+>/g,"").toLowerCase();
                    var data_url = data.url;
                    var index_title = -1;
                    var index_content = -1;
                    var first_occur = -1;
                    // only match artiles with not empty titles and contents
                    if(data_title != '' && data_content != '') {
                        keywords.forEach(function(keyword, i) {
                            index_title = data_title.indexOf(keyword);
                            index_content = data_content.indexOf(keyword);
                            if( index_title < 0 && index_content < 0 ){
                                isMatch = false;
                            } else {
                                if (index_content < 0) {
                                    index_content = 0;
                                }
                                if (i == 0) {
                                    first_occur = index_content;
                                }
                            }
                        });
                    }
                    // show search results
                    if (isMatch) {
                        matchcounts += 1;
                        str += "<li><a href='"+ data_url +"' class='search-result-title'>"+ data_title +"</a>";
                        var content = data.content.trim().replace(/<[^>]+>/g,"");
                        if (first_occur >= 0) {
                            // cut out 100 characters
                            var start = first_occur - 20;
                            var end = first_occur + 80;
                            if(start < 0){
                                start = 0;
                            }
                            if(start == 0){
                                end = 50;
                            }
                            if(end > content.length){
                                end = content.length;
                            }
                            var match_content = content.substring(start, end);
                            // highlight all keywords
                            keywords.forEach(function(keyword){
                                var regS = new RegExp(keyword, "gi");
                                match_content = match_content.replace(regS, "<b class=\"search-keyword\">"+keyword+"</b>");
                            });
                            
                            str += "<p class=\"search-result\">" + match_content +"...</p>"
                        }
                        str += "</li>";
                    }
                })};
                str += "</ul>";
                if (matchcounts == 0) { str = '<div id="no-result"><i class="fa fa-frown-o fa-5x" /></div>' }
                if (keywords == "") { str = '<div id="no-result"><i class="fa fa-search fa-5x" /></div>' }
                $resultContent.innerHTML = str;
            });
            proceedsearch();
        }
    });}

    // handle and trigger popup window;
    $('.popup-trigger').mousedown(function(e) {
      e.stopPropagation();
      if (isfetched == false) {
        searchFunc(path, 'local-search-input', 'local-search-result');
      } else {
        proceedsearch();
      };

    });

    $('.popup-btn-close').click(function(e){
      $('.popup').hide();
      $(".popoverlay").remove();
      $('body').css('overflow', '');
    });
    $('.popup').click(function(e){
      e.stopPropagation();
    });
  </script>

  

  

  
  <script src="https://cdn1.lncld.net/static/js/av-core-mini-0.6.1.js"></script>
  <script>AV.initialize("Qv6ckEtL1pe3PJD10qoOLKtg-gzGzoHsz", "NXiHFodQfmI8oxkK6IThhjrF");</script>
  <script>
    function showTime(Counter) {
      var query = new AV.Query(Counter);
      var entries = [];
      var $visitors = $(".leancloud_visitors");

      $visitors.each(function () {
        entries.push( $(this).attr("id").trim() );
      });

      query.containedIn('url', entries);
      query.find()
        .done(function (results) {
          var COUNT_CONTAINER_REF = '.leancloud-visitors-count';

          if (results.length === 0) {
            $visitors.find(COUNT_CONTAINER_REF).text(0);
            return;
          }

          for (var i = 0; i < results.length; i++) {
            var item = results[i];
            var url = item.get('url');
            var time = item.get('time');
            var element = document.getElementById(url);

            $(element).find(COUNT_CONTAINER_REF).text(time);
          }
          for(var i = 0; i < entries.length; i++) {
            var url = entries[i];
            var element = document.getElementById(url);
            var countSpan = $(element).find(COUNT_CONTAINER_REF);
            if( countSpan.text() == '') {
              countSpan.text(0);
            }
          }
        })
        .fail(function (object, error) {
          console.log("Error: " + error.code + " " + error.message);
        });
    }

    function addCount(Counter) {
      var $visitors = $(".leancloud_visitors");
      var url = $visitors.attr('id').trim();
      var title = $visitors.attr('data-flag-title').trim();
      var query = new AV.Query(Counter);

      query.equalTo("url", url);
      query.find({
        success: function(results) {
          if (results.length > 0) {
            var counter = results[0];
            counter.fetchWhenSave(true);
            counter.increment("time");
            counter.save(null, {
              success: function(counter) {
                var $element = $(document.getElementById(url));
                $element.find('.leancloud-visitors-count').text(counter.get('time'));
              },
              error: function(counter, error) {
                console.log('Failed to save Visitor num, with error message: ' + error.message);
              }
            });
          } else {
            var newcounter = new Counter();
            /* Set ACL */
            var acl = new AV.ACL();
            acl.setPublicReadAccess(true);
            acl.setPublicWriteAccess(true);
            newcounter.setACL(acl);
            /* End Set ACL */
            newcounter.set("title", title);
            newcounter.set("url", url);
            newcounter.set("time", 1);
            newcounter.save(null, {
              success: function(newcounter) {
                var $element = $(document.getElementById(url));
                $element.find('.leancloud-visitors-count').text(newcounter.get('time'));
              },
              error: function(newcounter, error) {
                console.log('Failed to create');
              }
            });
          }
        },
        error: function(error) {
          console.log('Error:' + error.code + " " + error.message);
        }
      });
    }

    $(function() {
      var Counter = AV.Object.extend("Counter");
      if ($('.leancloud_visitors').length == 1) {
        addCount(Counter);
      } else if ($('.post-title-link').length > 1) {
        showTime(Counter);
      }
    });
  </script>



  
<script type="text/javascript" src="/js/src/particle.js" count="50" zindex="-2" opacity="1" color="0,104,183"></script>
</body>
</html>
